Codeforces Round #656 Div3 A~F题解

A. Three Pairwise Maximums
题目大意：找到一组$(a,b,c)$使给定的$(x,y,z)$满足$x = max(a,b)$，$y = max(a,c)$，$z = max(b,c)$。你可以任意地输出$a,b,c$三个数而不用管顺序。
数据范围：
多组测试数据
$int$范围内

由于说$a,b,c$可以任意输出，所以这个题多半是一个比较弱的结论题。首先由于三个数都和$max$有关，所以最直接的一种想法就是找三个数里的最大值和最小值，最后一个可能是任意的。经过分析之后，第三个值应该取最小值，由于是取$max$故避免最小值无法取到的情况。最后把三个数的六种情况都$check$一下就知道是否是正确的了。
代码：

#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int x,y,z;
bool check(int a,int b,int c)
{
	if(x != max(a,b) || y != max(a,c) || z != max(b,c))	return 0;
	return 1;
}
int main()
{
    int T;scanf("%d",&T);
    while(T--)
    {
		scanf("%d%d%d",&x,&y,&z);
		int maxv = max({x,y,z});
		int minv = min({x,y,z});
		int half = maxv + minv >> 1;
		int a = maxv,b = minv,c = minv;
		if(check(a,b,c) || check(a,c,b) || check(b,a,c) || check(b,c,a) || check(c,a,b) || check(c,b,a))
		{
			puts("YES");
			printf("%d %d %d\n",a,b,c);
		}
		else puts("NO");
    }
    return 0;
}

B. Restore the Permutation by Merger
题目大意：本来有一个排列数列$p$，现在把$p$复制一份，让第二份插入到第一份中形成一个$2n$长度的序列，插入操作即顺次把第二份中的每一个元素插入第一份里，且必须要顺次的放进序列，现要求把原有的数列$p$求出来。
数据范围：
多组测试数据
$1 \leq n \leq 50$

乍一看$n$只有$50$，感觉可能是什么搜索题，不过经过分析之后可以发现题目里所说的插入操作由于说不能往之前插入的位置的前面放，所以相对顺序是不变的，每个元素的第一个产生位置累计起来就是原有的序列$p$。用$set$查重即可。

代码：

#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int main()
{
    int T;scanf("%d",&T);
    while(T--)
    {
		int n;scanf("%d",&n);
		vector<int> a(n * 2 +  7,0);
		for(int i = 1;i <= n * 2;++i)	scanf("%d",&a[i]);
		// for(int i = 1;i <= n * 2;++i)	printf("%d ",a[i]);puts("");
		set<int> st;
		vector<int> res;
		for(int i = 1;i <= n * 2;++i)
			if(!st.count(a[i]))
			{
				res.push_back(a[i]);
				st.insert(a[i]);
			}
		for(int i = 0;i < n;++i)	printf("%d ",res[i]);
		puts("");
    }
    return 0;
}

C. Make It Good
题目大意：给定一个长度为$n$的序列$\{a\}$，问最少要删掉几个$\{a\}$开头的元素，使得剩下的序列$b$是牛逼的。定义一个牛逼数列的条件是：$m$为数列长度，若序列可以在$m$次操作之后形成一个不降序列，则称数列为牛逼的，其中，一次操作是把序列里起始和末尾的元素拿出来放入一个新的序列$c$，最终要使$c$是不降的。

数据范围：
多组测试数据
$1 \leq n \leq 2 *10 ^ 5$
$1 \leq a_i \leq n$
元素可以重复

这个题由于说数据范围很大，最终做法是一个$O(n)$的或者带个$log$的，所以复杂度上就提示我们最多也就说遍历，或者排序。从遍历的角度来说，肯定是要找到一个易于判断的结论的，通过手玩几组比较短的数据可以发现，如果说出现了不合法的情况，那么问题是出在“谷底”的，即某一位元素是$a_{i-1} > a_i$并且$a_{i +1} > a_i$，因为在这种情况下，出现了一个$a_i$被夹在中间，这样的话这个$a_i$就会违反规则。所以答案已经很明显了，就是找到最后一个谷底，他的前面一位就是前缀要删除的数量。
不过到这里，实际上还没考虑完整个问题的全貌：因为元素是可以重复的，这个做法根本没考虑重复元素的问题。比如说$5 2 2 2 3$这组数据就会错误的判断为$0$，实际上是$1$。不难发现：对于一段连续的重复数字来说，只有这一段的值，和左右两个端点的下标有价值，所以先进行预处理：把重复元素全缩成一个$Node$包含$l,r,v$三个信息，最后如果出现了谷底，答案就是中间的$Node$的$l - 1$。

代码：

#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int N = 2e5 + 7;
int a[N];
struct Node{int l,r,v;};
int main()
{
    int T;scanf("%d",&T);
    while(T--)
    {
		int n;scanf("%d",&n);
		vector<Node> rg;
		for(int i = 1;i <= n;++i)	scanf("%d",&a[i]);
		int res = 0,last = 1;
		int l = 1,r = 1;
		
		while(r <= n)
		{
			while(a[r] == a[l])	++r;
			rg.push_back({l,r - 1,a[l]});
			l = r;
		}
		for(int i = rg.size() - 2;i >= 1;--i)
		{
			if(rg[i - 1].v > rg[i].v && rg[i + 1].v > rg[i].v)
			{
				res = rg[i].l - 1;
				break;
			}
		}
		printf("%d\n",res);
    }	
    return 0;
}

D. a-Good String
题目大意：给定一个字符串$s$，其长度为$n$，且$n$保证是$2$的幂。定义一个字符串是$c-$牛逼的，满足以下任意一个条件：
①长度为$1$，且$s_1=c$
②长度$>1$，且前半部分($s_1,s_2,s_3...s_{n/2}$)全是$c$，后半部分是一个$(c+1)-$牛逼的字符串。
③长度$>1$，且后半部分($s_{n/2+1},s_{n/2+2},...,s_n$)全是$c$，前半部分是一个$(c+1)-$牛逼的字符串。
现在你可以对任意一位的元素变换，问最少要几次变换，才能使得$s$是一个$a-$牛逼的字符串。

数据范围：
多组测试数据
$1 \leq n \leq 131072$
保证$\sum n \leq 2*10^5$

这题的数据量还是很大，初步考虑可能是一个$O(n)$或者带$log$的复杂度的算法。可以发现这个题的形式非常的偏向$log$：每次都是平分两段，让左边一段是怎样怎样，右边一段怎样怎样。想到这一步就能想到这个题的$key idea$：每次平分两个段，分别计算把左边变成一个$(c+1)-$牛逼的串加右边变成一个$c-$牛逼的字符串的代价；把左边变成一个$c-$牛逼的串加右边变成一个$(c+1)-$牛逼的串的代价。取较小者即可。具体实现的时候，可以采取递归的方式计算，递归基就是长度为$1$的串，一直向上传递结果并合并就可以算出来这个题了。
本题在具体实现的时候，如果采取传$string$的方式，有个众所周知的使用引用的方式，否则会$TLE$。当然，采取区间的方式也可以，就不用管传参的问题了。这里提供和$tutorial$一样的使用$string$传参的写法。

#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int slove(const string& s,char t)
{
	if(s.size() == 1)	return s[0] != t;
	int mid = s.size() / 2;
	int lf = slove(string(s.begin(),s.begin() + mid),t + 1);
	lf += mid - count(s.begin() + mid,s.end(),t);
	int rt = slove(string(s.begin() + mid,s.end()),t + 1);
	rt += mid - count(s.begin(),s.begin() + mid,t);
	return min(lf,rt);
}
int main()
{
	ios::sync_with_stdio(0);cin.tie(0);
	int T;cin >> T;
	while(T--)
	{
		int n;cin >> n;
		string s;cin >> s;
		cout << slove(s,'a') << endl;
	}
    return 0;
}

E. Directing Edges
题目大意：给定一个$n$点$m$边的联通图，有些边是有向的，而有些边是无向的。现在要给所有的无向边加一个方向，使得整个图变成一个$DAG$。若无解输出$-1$，反之将图中所有的边的连接信息输出。
注意：是所有边的链接信息。

数据范围：
多组测试数据
$2 \leq n \leq 2 * 10^5$

这题又不出意料的范围非常大。图里跟$DAG$有关的算法不多，也就一个$toposort$可能在这里用上。由于说整个图里还有无向边，又好像没有什么用了。不过还是先朝着这个方向想一下：把所有的无向边抠出去，只有有向边，求一次$toposort$。我们可以发现求完之后，如果已经是带环图了，必然无解；其次如果不带环，问题就变成了：怎么把没加进来的无向边规定一个方向，并保证不出现一个环？
手玩一下图可以发现如果出现了一个环，肯定是有一个点上至少有两条边，一条边一个连到了这个点头上来，这个点又连了一个出去，既然要规避有环的情况，就肯定是说让无向边的尽量外连就好了。具体来说，找到每个元素在拓扑排序里的位置，之后考虑所有边，对每条边来说，如果左端点在拓扑排序里的位置比右端点的早，那么就由左端点连右端点，反之亦然。而且可以发现这样构造是一定正确的，即不会出现环。

代码：

#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
vector<vector<int>> g;
vector<int> topo;
vector<int> used;
void dfs(int u)
{
	used[u] = 1;
	for(auto v : g[u])
		if(!used[v])
			dfs(v);
	topo.push_back(u);
}
int main()
{
    int T;scanf("%d",&T);
    while(T--)
    {

		int n,m;scanf("%d%d",&n,&m);
		g = vector<vector<int>>(n);
		vector<pii> edges;
		for(int i = 0;i < m;++i)
		{
			int t,u,v;scanf("%d%d%d",&t,&u,&v);
			--u;--v;
			if(t == 1)	g[u].push_back(v);
			edges.push_back({u,v});
		}
		used = vector<int> (n);
		topo.clear();
		for(int i = 0;i < n;++i)
			if(!used[i])
				dfs(i);
		reverse(topo.begin(),topo.end());
		vector<int> pos(n);
		for(int i = 0;i < n;++i)
			pos[topo[i]] = i;
		int ok = 1;
		for(int i = 0;i < n;++i)
		{
			for(auto j : g[i])
				if(pos[i] > pos[j])
				{
					ok = 0;
					break;
				}
			if(!ok)	break;
		}
		if(!ok)	puts("NO");
		else
		{
			puts("YES");
			for(auto [u,v] : edges)
			{
				if(pos[u] < pos[v])	printf("%d %d\n",u + 1,v + 1);
				else printf("%d %d\n",v + 1,u + 1);
			}			
		}
    }
    return 0;
}

F. Removing Leaves
题目大意：现给定一个$n$个点的树，定义一个操作：每次可以选择一个点，如果他与他直接连接的叶子有至少$k$个的话，则选择这个点以及$k$个叶子，将他们删去。问最多可以操作几次。
数据范围：
多组测试数据
$2 \leq n \leq 2 * 10^5$
$1 \leq k \leq n$

这题乍看像一个换根$dp$，复杂度应该是$O(n)$的，不过这题有一个用数据结构维护的做法：
明确一下问题：在整个树里动态的删除一些叶子，加入新的一些叶子。这可以用以平衡树为底层的$set$来实现，具体来说，我们做一个比较器$cmp$，使$set$能按子树的大小排序，每次迭代的时候取出所有还在树上的节点中子树大小最大的点，如果最大的都$< k$则直接退出，否则一直迭代下去。
在迭代过程中：每次取出一个叶子$leaf$，还要知道他的父亲，这个问题一会再说，假设我们已经知道了他的父亲是谁，那么现在要做的就是在邻接表中删去他俩的关系，以及存叶子节点的结构中删去$leaf$。之后如果父节点的大小也变成$1$了，就也加入叶子节点。具体更细致的维护关系看代码。

#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
vector<set<int>> leaves;
struct cmp
{
	bool operator()(int x,int y) const
	{
		if(leaves[x].size() == leaves[y].size())	return x < y;
		return leaves[x].size() > leaves[y].size();
	}
};


int main()
{
    int T;scanf("%d",&T);
    while(T--)
    {
		int n,k;scanf("%d%d",&n,&k);
		vector<set<int>> g(n + 1);
		leaves = vector<set<int>>(n + 1);
		for(int i = 1;i < n;++i)
		{
			int u,v;scanf("%d%d",&u,&v);
			g[u].insert(v);
			g[v].insert(u);
		}
		for(int i = 1;i <= n;++i)
			if(g[i].size() == 1)
				leaves[*g[i].begin()].insert(i);
		set<int,cmp> st;
		for(int i = 1;i <= n;++i)	st.insert(i);
		int res = 0;
		while(1)
		{
			int u = *st.begin();
			if(leaves[u].size() < k)	break;
			for(int i = 0;i < k;++i)
			{
				int leaf = *leaves[u].begin();
				g[leaf].erase(u);
				g[u].erase(leaf);
				st.erase(u);
				st.erase(leaf);
				leaves[u].erase(leaf);
				if(leaves[leaf].count(u))	leaves[leaf].erase(u);
				if(g[u].size() == 1)
				{
					int v = *g[u].begin();
					st.erase(v);
					leaves[v].insert(u);
					st.insert(v);
				}
				st.insert(u);
				st.insert(leaf);
			}
			++res;
		}
		printf("%d\n",res);
    }
    return 0;
}